﻿#ifndef TL_GRAPH_H
#define TL_GRAPH_H

#include "Utility.h"
#include "Vector.h"


namespace TL {
    template<class N, class C> class GraphEdge {
    public:
        N m_VertexNameFrom;
        N m_VertexNameTo;
        C m_Cost;
    };

    template<class N, class C> class Graph {
    public:
        Graph()
        {
            m_Directed = false;
            m_Weighted = false;
        }
        Graph(bool directed, bool weighted)
        {
            m_Directed = directed;
            m_Weighted = weighted;
        }

    public:
        void addEdge(N vertexNameFrom, N vertexNameTo, C edgeCost) // добавляет ребро
        {
            if(vertexNameFrom == vertexNameTo)
                return;

            if(!isVertexExist(vertexNameFrom) || !isVertexExist(vertexNameTo))
                return;

            if(isEdgeExist(vertexNameFrom, vertexNameTo))
                return;

            GraphEdge<N, C> newEdge;

            // настройка нового ребра
            newEdge.m_VertexNameFrom = vertexNameFrom;
            newEdge.m_VertexNameTo = vertexNameTo;
            newEdge.m_Cost = edgeCost;

            m_Edges.insert(m_Edges.size(), newEdge);

            if(!m_Directed) {
                newEdge.m_VertexNameFrom = vertexNameTo;
                newEdge.m_VertexNameTo = vertexNameFrom;

                m_Edges.insert(m_Edges.size(), newEdge);
            }
        }
        void addVertex(N vertexName) // добавляет вершину
        {
            if(isVertexExist(vertexName))
                return;

            m_Vertices.insert(m_Vertices.size(), vertexName);
        }
        C bellmanFord(N vertexNameFrom, N vertexNameTo)
        {
            GraphEdge<N, C> *pEdge;

            Vector<C> d(m_Vertices.size(), TL_INFINITY);
            d[getVertexNumber(vertexNameFrom)] = 0;

            for(;;) {
                bool any = false;

                for(int i = 0; i < m_Edges.size(); i++) {
                    pEdge = &m_Edges[i];

                    if(d[getVertexNumber(pEdge->m_VertexNameFrom)] < TL_INFINITY) {
                        if(d[getVertexNumber(pEdge->m_VertexNameTo)] > d[getVertexNumber(pEdge->m_VertexNameFrom)] + pEdge->m_Cost) {
                            d[getVertexNumber(pEdge->m_VertexNameTo)] = d[getVertexNumber(pEdge->m_VertexNameFrom)] + pEdge->m_Cost;
                            any = true;
                        }
                    }
                }

                if(!any)
                    break;
            }

            return d[getVertexNumber(vertexNameTo)];
        }
        Vector<N> bellmanFordPath(N vertexNameFrom, N vertexNameTo)
        {
            GraphEdge<N, C> *pEdge;

            Vector<C> d(m_Vertices.size(), TL_INFINITY);
            d[getVertexNumber(vertexNameFrom)] = 0;

            Vector<int> p(m_Vertices.size(), -1); // вектор номеров предпоследних вершин для каждой вершины

            for(;;) {
                bool any = false;

                for(int i = 0; i < m_Edges.size(); i++) {
                    pEdge = &m_Edges[i];

                    if(d[getVertexNumber(pEdge->m_VertexNameFrom)] < TL_INFINITY) {
                        if(d[getVertexNumber(pEdge->m_VertexNameTo)] > d[getVertexNumber(pEdge->m_VertexNameFrom)] + pEdge->m_Cost) {
                            d[getVertexNumber(pEdge->m_VertexNameTo)] = d[getVertexNumber(pEdge->m_VertexNameFrom)] + pEdge->m_Cost;
                            p[getVertexNumber(pEdge->m_VertexNameTo)] = getVertexNumber(pEdge->m_VertexNameFrom);
                            any = true;
                        }
                    }
                }

                if(!any)
                    break;
            }

            if(d[getVertexNumber(vertexNameTo)] == TL_INFINITY) {
                return Vector<N>();
            } else {
                 Vector<N> path;

                 for(int cur = getVertexNumber(vertexNameTo); cur != -1; cur=p[cur]) {
                     path << getVertexName(cur);
                 }

                 path.reverse();

                 return path;
            }
        }
        void clear() // удаляет все вершины и ребра
        {
            m_Vertices.clear();
            m_Edges.clear();
        }
        Vector<N> getAdjacentVertices(N vertexName) // возвращает вектор имен смежных вершин
        {
            if(!isVertexExist(vertexName))
                return Vector<N>();

            GraphEdge<N, C> *pEdge;
            Vector<N> adjVector;

            for(int i = 0; i < m_Edges.size(); i++) {
                pEdge = &m_Edges[i];

                if(pEdge->m_VertexNameFrom == vertexName)
                    adjVector.insert(adjVector.size(), pEdge->m_VertexNameTo);
            }

            return adjVector;
        }
        C getEdgeWeight(N vertexNameFrom, N vertexNameTo) // возвращает вес ребра
        {
            if(!m_Weighted)
                return C(); // ребра не имеют веса
            
            GraphEdge<N, C> *pEdge;

            for(int i = 0; i < m_Edges.size(); i++) {
                pEdge = &m_Edges[i];

                if(pEdge->m_VertexNameFrom == vertexNameFrom && pEdge->m_VertexNameTo == vertexNameTo)
                    return pEdge->m_Cost;
            }

            return C(); // не найдено
        }
        N getVertexName(int vertexNumber) // возвращает имя вершины по ее номеру
        {
            if(vertexNumber < 0 || vertexNumber > m_Vertices.size()-1)
                return N();
            
            return m_Vertices[vertexNumber];
        }
        int getVertexNumber(N vertexName) // возвращает номер вершины по ее имени
        {
            for(int i = 0; i < m_Vertices.size(); i++) {
                if(m_Vertices[i] == vertexName)
                    return i;
            }

            return -1;
        }
        int getVerticesCount() // возвращает количество вершин
        {
            return m_Vertices.size();
        }
        bool isEdgeExist(N vertexNameFrom, N vertexNameTo) // проверяет, существует ли ребро
        {
            GraphEdge<N, C> *pEdge;

            for(int i = 0; i < m_Edges.size(); i++) {
                pEdge = &m_Edges[i];

                if(pEdge->m_VertexNameFrom == vertexNameFrom && pEdge->m_VertexNameTo == vertexNameTo)
                    return true;
            }

            return false;
        }
        bool isVertexExist(N vertexName) // проверяет, существует ли вершина
        {
            for(int i = 0; i < m_Vertices.size(); i++) {
                if(m_Vertices[i] == vertexName)
                    return true;
            }

            return false;
        }
        void removeEdge(N vertexNameFrom, N vertexNameTo) // удаляет ребро
        {
            GraphEdge<N, C> *pEdge;

            for(int i = 0; i < m_Edges.size(); i++) {
                pEdge = &m_Edges[i];

                if(pEdge->m_VertexNameFrom == vertexNameFrom && pEdge->m_VertexNameTo == vertexNameTo) {
                    m_Edges.remove(i);

                    if(!m_Directed) {
                        // дублированное ребро идет вслед за исходным, так что после его удаления, нужно удалить следующее ребро
                        m_Edges.remove(i);
                    }
                    return;
                }
            }
        }
        void removeVertex(N vertexName) // удаляет вершину
        {
            if(!isVertexExist(vertexName))
                return;

            m_Vertices.remove(getVertexNumber(vertexName));

            update_edges();
        }

    public:
#ifdef _IOSTREAM_
        friend std::ostream &operator<<(std::ostream &stream, Graph<N, C> &graph)
        {
            Vector<N> adjVector;

            for(int i = 0; i < graph.m_Vertices.size(); i++) {
                stream << (i > 0 ? "\nVertex \"" : "Vertex \"") << graph.m_Vertices[i] << "\"";

                adjVector = graph.getAdjacentVertices(graph.m_Vertices[i]);

                if(adjVector.size() > 1) {
                    stream << " has " << adjVector.size() << " edges:";

                    for(int j = 0; j < adjVector.size(); j++) {
                        stream << " \"" << adjVector[j] << "\"";

                        if(graph.m_Weighted)
                            stream << "(" << graph.getEdgeWeight(graph.m_Vertices[i], adjVector[j]) << ")";
                    }
                } else if(adjVector.size() == 1) {
                    stream << " has 1 edge:";

                    stream << " \"" << adjVector[0] << "\"";

                    if(graph.m_Weighted)
                        stream << "(" << graph.getEdgeWeight(graph.m_Vertices[i], adjVector[0]) << ")";
                } else {
                    stream << " has no edges";
                }
            }

            return stream;
        }
#endif
    
    private:
        Vector<N> m_Vertices;
        Vector<GraphEdge<N, C>> m_Edges;
        bool m_Directed; // ориентированный
        bool m_Weighted; // взвешенный

    private:
        void update_edges() // удаляет несуществующие ребра
        {
            GraphEdge<N, C> *pEdge;
            bool start, end;
            int i = 0;

            while(i < m_Edges.size()) {
                pEdge = &m_Edges[i];

                start = false;
                end = false;

                for(int j = 0; j < m_Vertices.size() && (!start || !end); j++) {
                    if(pEdge->m_VertexNameFrom == m_Vertices[j])
                        start = true; // начальная вершина найдена

                    if(pEdge->m_VertexNameTo == m_Vertices[j])
                        end = true; // конечная вершина найдена
                }

                if(start && end) {
                    i++;
                } else {
                    m_Edges.remove(i);
                }
            }
        }
    };
}

#endif